{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Eaten Apples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: eatenApples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #吃苹果的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一棵特殊的苹果树，一连 <code>n</code> 天，每天都可以长出若干个苹果。在第 <code>i</code> 天，树上会长出 <code>apples[i]</code> 个苹果，这些苹果将会在 <code>days[i]</code> 天后（也就是说，第 <code>i + days[i]</code> 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 <code>apples[i] == 0</code> 且 <code>days[i] == 0</code> 表示。</p>\n",
    "\n",
    "<p>你打算每天 <strong>最多</strong> 吃一个苹果来保证营养均衡。注意，你可以在这 <code>n</code> 天之后继续吃苹果。</p>\n",
    "\n",
    "<p>给你两个长度为 <code>n</code> 的整数数组 <code>days</code> 和 <code>apples</code> ，返回你可以吃掉的苹果的最大数目<em>。</em></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>apples = [1,2,3,5,2], days = [3,2,1,4,2]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>你可以吃掉 7 个苹果：\n",
    "- 第一天，你吃掉第一天长出来的苹果。\n",
    "- 第二天，你吃掉一个第二天长出来的苹果。\n",
    "- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。\n",
    "- 第四天到第七天，你吃的都是第四天长出来的苹果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>你可以吃掉 5 个苹果：\n",
    "- 第一天到第三天，你吃的都是第一天长出来的苹果。\n",
    "- 第四天和第五天不吃苹果。\n",
    "- 第六天和第七天，你吃的都是第六天长出来的苹果。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>apples.length == n</code></li>\n",
    "\t<li><code>days.length == n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= apples[i], days[i] &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li>只有在 <code>apples[i] = 0</code> 时，<code>days[i] = 0</code> 才成立</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-eaten-apples](https://leetcode.cn/problems/maximum-number-of-eaten-apples/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-eaten-apples](https://leetcode.cn/problems/maximum-number-of-eaten-apples/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,5,2]\\n[3,2,1,4,2]', '[3,0,0,0,0,2]\\n[3,0,0,0,0,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        h = []\n",
    "        i = ans = 0\n",
    "        while h or i < len(days):\n",
    "            if i < len(days) and apples[i] > 0:\n",
    "                heapq.heappush(h, (i + days[i], apples[i]))\n",
    "            while h and h[0][0] <= i:\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                day, cnt = heapq.heappop(h)\n",
    "                ans += 1\n",
    "                if cnt > 1: heapq.heappush(h, (day, cnt - 1))\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\r\n",
    "        # 贪心每次先吃最早要腐烂的\r\n",
    "\r\n",
    "        pq = []\r\n",
    "        res = 0\r\n",
    "        i = 0\r\n",
    "        while i < len(apples) or pq:\r\n",
    "            if i < len(apples) and apples[i]:\r\n",
    "                heappush(pq, (days[i] + i - 1, apples[i]))\r\n",
    "            while pq and pq[0][0] < i:\r\n",
    "                heappop(pq)\r\n",
    "            if pq:\r\n",
    "                res += 1 \r\n",
    "                if pq[0][1] > 1:\r\n",
    "                    heapreplace(pq,(pq[0][0], pq[0][1] - 1))\r\n",
    "                else:\r\n",
    "                    heappop(pq)      \r\n",
    "            i += 1 \r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(apples)\n",
    "        mheap = []\n",
    "        \n",
    "        d = 0\n",
    "        while d<n or mheap:\n",
    "            if d<n:\n",
    "                anum,day = apples[d],days[d]\n",
    "                if anum>0:\n",
    "                    heapq.heappush(mheap, (d+day, anum))\n",
    "            while mheap and mheap[0][0]<=d:\n",
    "                heapq.heappop(mheap)\n",
    "            if mheap:\n",
    "                eday, anum = heapq.heappop(mheap)\n",
    "                anum -= 1\n",
    "                res += 1\n",
    "                if anum>0:\n",
    "                    heapq.heappush(mheap, (eday, anum))\n",
    "            d+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        h = []\n",
    "        i = ans = 0\n",
    "        while h or i < len(days):\n",
    "            if i < len(days) and apples[i] > 0:\n",
    "                heapq.heappush(h, (i + days[i], apples[i]))\n",
    "            while h and h[0][0] <= i:\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                day, cnt = heapq.heappop(h)\n",
    "                ans += 1\n",
    "                if cnt > 1: heapq.heappush(h, (day, cnt - 1))\n",
    "            i += 1\n",
    "        return ans\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        d = SortedDict()\n",
    "        res = 0\n",
    "        for a, day, i in zip_longest(apples, days, range(40000)):\n",
    "            if not d and a==None: break\n",
    "            if a:\n",
    "                if i+day-1 not in d: d[i+day-1] = a\n",
    "                else: d[i+day-1] += a\n",
    "            if d:\n",
    "                d[d.keys()[0]] -= 1\n",
    "                res += 1\n",
    "            while d and (d.keys()[0]<=i or d[d.keys()[0]]==0): d.pop(d.keys()[0])\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        # 堆维护截止日期最小的苹果个数，注意不能先全部放进堆\n",
    "        # 因为不能先吃未来的苹果\n",
    "        res = 0\n",
    "        n = len(apples)\n",
    "        mheap = []\n",
    "        \n",
    "        d = 0\n",
    "        while d<n or mheap:\n",
    "            if d<n:\n",
    "                anum,day = apples[d],days[d]\n",
    "                if anum>0:\n",
    "                    heapq.heappush(mheap, (d+day, anum))\n",
    "            while mheap and mheap[0][0]<=d:\n",
    "                heapq.heappop(mheap)\n",
    "            if mheap:\n",
    "                eday, anum = heapq.heappop(mheap)\n",
    "                anum -= 1\n",
    "                res += 1\n",
    "                if anum>0:\n",
    "                    heapq.heappush(mheap, (eday, anum))\n",
    "            d+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        info = []\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(apples)):\n",
    "            if apples[i] > 0:\n",
    "                heapq.heappush(info, (i + days[i], apples[i]))\n",
    "\n",
    "            \n",
    "            while info and info[0][0] <= i:\n",
    "                heapq.heappop(info)\n",
    "            \n",
    "            \n",
    "            if info:\n",
    "                if info[0][1] == 1:\n",
    "                    heapq.heappop(info)\n",
    "                    res += 1\n",
    "                else:\n",
    "                    res += 1\n",
    "                    info[0] = (info[0][0], info[0][1] - 1)\n",
    "        \n",
    "        t = len(apples)\n",
    "        while info:\n",
    "            while info and info[0][0] <= t:\n",
    "                heapq.heappop(info)\n",
    "            \n",
    "            \n",
    "            if info:\n",
    "                if info[0][1] == 1:\n",
    "                    heapq.heappop(info)\n",
    "                    res += 1\n",
    "                else:\n",
    "                    res += 1\n",
    "                    info[0] = (info[0][0], info[0][1] - 1)\n",
    "            \n",
    "            t += 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        # 怎样吃的苹果尽可能多，每次都从为芙兰的苹果中选出过期时间最小的苹果吃掉，知道堆变成空\n",
    "        # 如果对顶元素时间小于day,那么弹出元素，知道堆顶元素时间大于等于day,如果堆为空，说明第day没有苹果，return 天数\n",
    "        n = len(apples)\n",
    "        if n == 0: return 0\n",
    "        pq = []\n",
    "        t = 0\n",
    "        from heapq import heapreplace, heappush, heappop\n",
    "        cnt = 0\n",
    "        while t<n or pq:\n",
    "            while pq and pq[0][0] <= t:\n",
    "                heappop(pq)\n",
    "            if t < n and apples[t]:\n",
    "                heappush(pq, (t + days[t], apples[t]))\n",
    "            if pq:\n",
    "                if pq[0][1] > 1:\n",
    "                    heapreplace(pq, (pq[0][0], pq[0][1] - 1))\n",
    "                else:\n",
    "                    heappop(pq)\n",
    "                cnt += 1\n",
    "            t += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        h = []\n",
    "        i = ans = 0\n",
    "        while h or i < len(days):\n",
    "            if i < len(days) and apples[i] > 0:\n",
    "                heapq.heappush(h, (i + days[i], apples[i]))\n",
    "            while h and h[0][0] <= i:\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                day, cnt = heapq.heappop(h)\n",
    "                ans += 1\n",
    "                if cnt > 1: heapq.heappush(h, (day, cnt - 1))\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        from heapq import heappush, heappop\n",
    "\n",
    "        store = []\n",
    "        res = 0\n",
    "\n",
    "        def eat():\n",
    "            if not store:\n",
    "                return\n",
    "\n",
    "            nonlocal res\n",
    "            res += 1\n",
    "\n",
    "            if store[0][1] == 1:\n",
    "                heappop(store)\n",
    "            else:\n",
    "                store[0] = (store[0][0], store[0][1] - 1)\n",
    "\n",
    "        n = len(apples)\n",
    "        for day in range(n):\n",
    "            while store and store[0][0] <= day:\n",
    "                heappop(store)\n",
    "\n",
    "            if apples[day] != 0:\n",
    "                heappush(store, (day + days[day], apples[day]))\n",
    "\n",
    "            eat()\n",
    "\n",
    "        while store:\n",
    "            day += 1\n",
    "            while store and store[0][0] <= day:\n",
    "                heappop(store)\n",
    "\n",
    "            eat()\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        heap = []\n",
    "        res = 0\n",
    "        n = len(apples)\n",
    "        i = 0\n",
    "\n",
    "        while i < n or heap:\n",
    "            if i < n:\n",
    "                heapq.heappush(heap, (i+days[i]-1, apples[i]))\n",
    "            # print(i, heap)\n",
    "            while heap and heap[0][0] < i:\n",
    "                heapq.heappop(heap)\n",
    "            if heap:\n",
    "                res += 1\n",
    "                if heap[0][1] > 1:\n",
    "                    heap[0] = (heap[0][0], heap[0][1]-1)\n",
    "                else:\n",
    "                    heapq.heappop(heap)\n",
    "            i += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        #越早过期\n",
    "        heap = []\n",
    "        cnt = 0\n",
    "        day = 0\n",
    "        while day < len(days) or heap:\n",
    "            while heap and heap[0][0] <= day:\n",
    "                heapq.heappop(heap)\n",
    "            if day < len(days) and apples[day] > 0:\n",
    "                heapq.heappush(heap, (day + days[day], apples[day]))\n",
    "            if heap:\n",
    "                top = heapq.heappop(heap)\n",
    "                left = top[1] - 1\n",
    "                cnt += 1\n",
    "                if left:\n",
    "                    heapq.heappush(heap, (top[0], top[1] - 1))\n",
    "            while heap and heap[0][0] <= day:\n",
    "                heapq.heappop(heap)\n",
    "            day += 1\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        a = []\n",
    "        total = 0\n",
    "        cnt = 0\n",
    "        flag = [0]*(len(apples)+30000)\n",
    "            \n",
    "\n",
    "\n",
    "        for i in range(len(apples)+30000):\n",
    "            if i<len(apples):\n",
    "                if i+days[i] not in a:\n",
    "                    a.append(i+days[i])\n",
    "                    a = sorted(a)\n",
    "                flag[i+days[i]] = flag[i+days[i]] + apples[i]\n",
    "            # print(a)\n",
    "            \n",
    "            if len(a)>0 and i == a[0]:\n",
    "                total = total - flag[a[0]]\n",
    "                a.pop(0)\n",
    "            if i>=len(apples) and len(a)==0:\n",
    "                break\n",
    "            if i<len(apples) and apples[i] == 0 and total == 0:\n",
    "                continue\n",
    "            if i<len(apples):\n",
    "                total = total + apples[i]\n",
    "            cnt = cnt+1\n",
    "            flag[a[0]] = flag[a[0]]-1\n",
    "            total = total-1\n",
    "            if flag[a[0]] == 0:\n",
    "                # total = total - flag[a[0]]\n",
    "                a.pop(0)\n",
    "            if i>=len(apples) and len(a)==0:\n",
    "                break\n",
    "        \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        n = len(apples)\n",
    "\n",
    "        heap = []\n",
    "        ans = 0\n",
    "\n",
    "        now = 0\n",
    "\n",
    "        while now < n or heap:\n",
    "            # 先接收当天的苹果\n",
    "            if now < n:\n",
    "                heapq.heappush(heap, (now + days[now], apples[now]))\n",
    "\n",
    "            # 再腐烂旧苹果\n",
    "            while heap and (heap[0][0] <= now or heap[0][1] == 0):\n",
    "                heapq.heappop(heap)\n",
    "\n",
    "            if heap:\n",
    "                heap[0] = (heap[0][0], heap[0][1] - 1)\n",
    "                ans += 1\n",
    "\n",
    "            now += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        queue = []\n",
    "        res = 0\n",
    "        for i in range(len(apples)):\n",
    "            heapq.heappush(queue, [i+days[i], apples[i]])\n",
    "\n",
    "            while queue and queue[0][0] <= i:\n",
    "                heapq.heappop(queue)\n",
    "            \n",
    "            if queue and queue[0][1] > 0:\n",
    "                res += 1\n",
    "                queue[0][1] -= 1\n",
    "                if queue[0][1] == 0:\n",
    "                    heapq.heappop(queue)\n",
    "        \n",
    "        day = len(days)\n",
    "        while queue:\n",
    "            ddl, remain = heapq.heappop(queue)\n",
    "            if ddl <= day:\n",
    "                continue\n",
    "            cnt = min(remain, ddl-day)\n",
    "            day += cnt\n",
    "            res += cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        heap = []\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < len(apples) or heap:\n",
    "            if i < len(apples) and apples[i] > 0:\n",
    "                heapq.heappush(heap, (i + days[i], apples[i]))\n",
    "            while heap and heap[0][0] <= i:\n",
    "                heapq.heappop(heap)\n",
    "            if heap:\n",
    "                d, a = heapq.heappop(heap)\n",
    "                ans += 1\n",
    "                if a > 1:\n",
    "                    heapq.heappush(heap, (d, a - 1))\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        n = len(apples)\n",
    "        heap = []\n",
    "        result = 0\n",
    "        i = 0\n",
    "        while(i < n or heap):\n",
    "            if(i < n and apples[i] > 0):\n",
    "                heapq.heappush(heap, [i+days[i], apples[i]])\n",
    "            if(heap):\n",
    "                d, cnt = heapq.heappop(heap)\n",
    "                while(heap and d <= i):\n",
    "                    d, cnt = heapq.heappop(heap)\n",
    "                if(i < d):\n",
    "                    result += 1\n",
    "                    cnt -= 1\n",
    "                    if(cnt > 0):\n",
    "                        heapq.heappush(heap, [d,cnt])\n",
    "            i += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        #越早过期\n",
    "        heap = []\n",
    "        cnt = 0\n",
    "        day = 0\n",
    "        while day < len(days) or heap:\n",
    "            while heap and heap[0][0] <= day:\n",
    "                heapq.heappop(heap)\n",
    "            if day < len(days) and apples[day] > 0:\n",
    "                heapq.heappush(heap, (day + days[day], apples[day]))\n",
    "            if heap:\n",
    "                top = heapq.heappop(heap)\n",
    "                left = top[1] - 1\n",
    "                cnt += 1\n",
    "                if left:\n",
    "                    heapq.heappush(heap, (top[0], top[1] - 1))\n",
    "            # while heap and heap[0][0] <= day:\n",
    "            #     heapq.heappop(heap)\n",
    "            day += 1\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        apple_list = []\n",
    "        res = 0\n",
    "        for idx, apl_num in enumerate(apples):\n",
    "            if apl_num:\n",
    "                apple_today = [idx + days[idx] - 1, apl_num]\n",
    "                bisect.insort_left(apple_list, apple_today)\n",
    "            while apple_list and apple_list[0][0] < idx:\n",
    "                apple_list.pop(0)\n",
    "            if apple_list:\n",
    "                apple_list[0][1] -= 1\n",
    "                res += 1\n",
    "                if not apple_list[0][1]:\n",
    "                    apple_list.pop(0)\n",
    "        day = len(apples) - 1\n",
    "        for ap in apple_list:\n",
    "            live = ap[0]\n",
    "            num = ap[1]\n",
    "            add_num = min(num, live - day)\n",
    "            day += add_num\n",
    "            res += add_num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        # 模板：使用堆进行贪心模拟\n",
    "        n = len(apples)\n",
    "        ans = i = 0\n",
    "        stack = []\n",
    "        while i < n or stack:\n",
    "            if i < n and apples[i]:\n",
    "                heappush(stack, [i+days[i]-1, apples[i]])\n",
    "            while stack and (stack[0][0] < i or not stack[0][1]):\n",
    "                heappop(stack)\n",
    "            if stack:\n",
    "                stack[0][1] -= 1\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        tmp = []     \n",
    "        n = len(apples)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            heapq.heappush(tmp, (i+days[i], apples[i]))\n",
    "            while tmp:\n",
    "                last, num = heapq.heappop(tmp)\n",
    "                if i < last and num:\n",
    "                    res += 1\n",
    "                    heapq.heappush(tmp, (last, num-1))\n",
    "                    break\n",
    "        while tmp:\n",
    "            last, num = heapq.heappop(tmp)\n",
    "            if n < last and num:\n",
    "                res += 1\n",
    "                n += 1\n",
    "                heapq.heappush(tmp, (last, num-1))    \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        pq = []\n",
    "        n = len(apples)\n",
    "        ret = 0\n",
    "        for day in range(n):\n",
    "            heapq.heappush(pq, (day+1+days[day], apples[day]))\n",
    "            time, num = heapq.heappop(pq)\n",
    "            while pq and (time-1 <= day or num <= 0):\n",
    "                time, num = heapq.heappop(pq)\n",
    "            # print(ret, day, pq,\"??\")\n",
    "            if time-1 > day and num > 0:\n",
    "                ret += 1\n",
    "                heapq.heappush(pq, (time, num-1))            \n",
    "            # print(ret, day, pq)\n",
    "        day = n\n",
    "        while pq:\n",
    "            # print(ret, day, pq)\n",
    "            time, num = heapq.heappop(pq)\n",
    "            if time-1 > day and num > 0:\n",
    "                ret += 1\n",
    "                day += 1\n",
    "                heapq.heappush(pq, (time, num-1))\n",
    "        \n",
    "        return ret\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "\n",
    "        start, end = -1,-1 \n",
    "\n",
    "        \n",
    "        extend = max( [  i+days[i]-1  for i,x in enumerate(apples)])   \n",
    "        n = len(apples)\n",
    "        heap = []\n",
    "\n",
    "        cnt = 0 \n",
    "        for i in range(extend+1):\n",
    "   \n",
    "            if i<n and apples[i]>0:\n",
    "                heapq.heappush(heap, (i+days[i]-1, apples[i]))\n",
    "            \n",
    "            while heap:\n",
    "                x,y = heap[0]\n",
    "                if x<i:\n",
    "                    heapq.heappop(heap)\n",
    "                else:\n",
    "                    break \n",
    "            #print(i,heap)\n",
    "            if heap:\n",
    "                x,y = heap[0]\n",
    "                if x>=i:\n",
    "                    cnt +=1 \n",
    "                    heapq.heappop(heap)\n",
    "                    if y-1>0:\n",
    "                        heapq.heappush(heap, (x,y-1))\n",
    "        return cnt \n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pq = []\n",
    "        i = 0\n",
    "        while i < len(apples):\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heappop(pq)\n",
    "            if apples[i]:\n",
    "                heappush(pq, [i + days[i], apples[i]])\n",
    "            if pq:\n",
    "                pq[0][1] -= 1\n",
    "                if pq[0][1] == 0:\n",
    "                    heappop(pq)\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        while pq:\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heappop(pq)\n",
    "            if len(pq) == 0:\n",
    "                break\n",
    "            p = heappop(pq)\n",
    "            num = min(p[0] - i, p[1])\n",
    "            ans += num\n",
    "            i += num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        tmp = []     \n",
    "        n = len(apples)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            heapq.heappush(tmp, (i+days[i], apples[i]))\n",
    "            while tmp:\n",
    "                last, num = heapq.heappop(tmp)\n",
    "                if i < last and num:\n",
    "                    res += 1\n",
    "                    heapq.heappush(tmp, (last, num-1))\n",
    "                    break\n",
    "        \n",
    "        while tmp:\n",
    "            last, num = heapq.heappop(tmp)\n",
    "            if n < last and num:\n",
    "                res += 1\n",
    "                n += 1\n",
    "                heapq.heappush(tmp, (last, num-1))    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        import collections,heapq\n",
    "        n = len(apples)\n",
    "        nums = collections.defaultdict(int)\n",
    "        store = []\n",
    "        heapq.heapify(store)\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < n or store: \n",
    "            if i < n:              \n",
    "                last = i + days[i] - 1 if days[i] > 0 else 0\n",
    "                nums[last] += apples[i] #保质期\n",
    "                if last not in store and days[i] != 0:\n",
    "                        heapq.heappush(store,last)\n",
    "            \n",
    "            while store and store[0] < i:\n",
    "                heapq.heappop(store)\n",
    "            if store and nums.get(store[0],0):\n",
    "                cnt += 1\n",
    "                nums[store[0]] -= 1\n",
    "                if nums[store[0]] == 0:\n",
    "                    heapq.heappop(store)\n",
    "            i += 1\n",
    "\n",
    "        return cnt \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        tmp = []     \n",
    "        n = len(apples)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            heapq.heappush(tmp, [i+days[i], apples[i]])\n",
    "            while tmp:\n",
    "                if i < tmp[0][0] and tmp[0][1]:\n",
    "                    res += 1\n",
    "                    tmp[0][1] -= 1\n",
    "                    break\n",
    "                else:\n",
    "                    heapq.heappop(tmp)\n",
    "        while tmp:\n",
    "            if n < tmp[0][0] and tmp[0][1]:\n",
    "                res += 1\n",
    "                tmp[0][1] -= 1\n",
    "                n += 1\n",
    "            else:\n",
    "                heapq.heappop(tmp)  \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        n = len(apples)\n",
    "        pq = []\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while True:\n",
    "            if i<n:\n",
    "                heapq.heappush(pq,[days[i]+i,apples[i]])\n",
    "            while pq:\n",
    "                if i<pq[0][0] and pq[0][1]>0:\n",
    "                    res+=1\n",
    "                    pq[0][1]-=1\n",
    "                    i+=1\n",
    "                    break\n",
    "                else:\n",
    "                    heapq.heappop(pq)\n",
    "            else:\n",
    "                if i<n:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    break\n",
    "        return res\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pq = []\n",
    "        i = 0\n",
    "        while i < len(apples):\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heappop(pq)\n",
    "            if apples[i]:\n",
    "                heappush(pq, [i + days[i], apples[i]])\n",
    "            if pq:\n",
    "                pq[0][1] -= 1\n",
    "                if pq[0][1] == 0:\n",
    "                    heappop(pq)\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        while pq:\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heappop(pq)\n",
    "            if len(pq) == 0:\n",
    "                break\n",
    "            p = heappop(pq)\n",
    "            num = min(p[0] - i, p[1])\n",
    "            ans += num\n",
    "            i += num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\r\n",
    "        # 巧用数据结构\r\n",
    "        n = len(apples)\r\n",
    "        ans = 0\r\n",
    "        i = 0\r\n",
    "        heap = []\r\n",
    "        while(i < n or heap):\r\n",
    "            if i < n and apples[i]:\r\n",
    "                heapq.heappush(heap, [i + days[i], apples[i]])\r\n",
    "            \r\n",
    "            while heap and (heap[0][0] <= i or heap[0][1] == 0):\r\n",
    "                heapq.heappop(heap)\r\n",
    "            \r\n",
    "            if heap:\r\n",
    "                heap[0] = [heap[0][0], heap[0][1] - 1]\r\n",
    "                ans += 1\r\n",
    "            \r\n",
    "            i += 1\r\n",
    "\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        #堆+贪心 优先队列\n",
    "        pq = [] #最小堆，队首是最小的 [i+days[i], apples[i]]\n",
    "        i = 0 #天数\n",
    "        ans = 0 #可以吃到的苹果数\n",
    "\n",
    "        #第一阶段 i <= n\n",
    "        while i < len(apples):\n",
    "            while pq and pq[0][0] <= i: #腐烂日期小于当前日期（=是因为i从0开始）\n",
    "                heappop(pq) #出队列，没用了\n",
    "            if apples[i] > 0: #当天生产苹果，入队列\n",
    "                heappush(pq, [i + days[i], apples[i]])\n",
    "            if pq: #还有苹果可吃\n",
    "                pq[0][1] -= 1\n",
    "                ans += 1 #吃苹果\n",
    "                if pq[0][1] == 0:\n",
    "                    heappop(pq)\n",
    "            i += 1\n",
    "        \n",
    "        #第二阶段 i > n时，不产苹果只消耗\n",
    "        while pq:\n",
    "            cur = heappop(pq)\n",
    "            res = min(cur[0]-i, cur[1])\n",
    "            i += res #当前天数加上去\n",
    "            ans += res #吃的苹果数直接加上去\n",
    "            while pq and pq[0][0] <= i: #再判断是否腐烂\n",
    "                heappop(pq)\n",
    "        return ans\n",
    "\n",
    "        #不能输出i, 因为可能中间不吃苹果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        tmp = []     \n",
    "        n = len(apples)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            heapq.heappush(tmp, [i+days[i], apples[i]])\n",
    "            while tmp:\n",
    "                if i < tmp[0][0] and tmp[0][1]:\n",
    "                    res += 1\n",
    "                    tmp[0][1] -= 1\n",
    "                    break\n",
    "                else:\n",
    "                    heapq.heappop(tmp)\n",
    "\n",
    "        while tmp:\n",
    "            last, num = heapq.heappop(tmp)\n",
    "            if n < last and num:\n",
    "                res += 1\n",
    "                n += 1\n",
    "                heapq.heappush(tmp, [last, num-1])    \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\r\n",
    "        # # 超时\r\n",
    "        # lis = [[i, -1] for i in range(len(days))]\r\n",
    "        # for i in range(len(days)):\r\n",
    "        #     if days[i] != 0:\r\n",
    "        #         lis[i][1] = i + days[i] - 1\r\n",
    "        # arr = sorted(lis, key=lambda x:(x[1], x[0]))\r\n",
    "        # print(arr)\r\n",
    "\r\n",
    "        # s = set()\r\n",
    "        # for i in range(len(arr)):\r\n",
    "        #     cnt = 0\r\n",
    "        #     if arr[i][1] != -1:\r\n",
    "        #         for k in range(arr[i][0], arr[i][1] + 1):\r\n",
    "        #             if cnt < apples[arr[i][0]]:\r\n",
    "        #                 if k not in s:\r\n",
    "        #                     s.add(k)\r\n",
    "        #                     cnt += 1\r\n",
    "        #             else:\r\n",
    "        #                 break\r\n",
    "\r\n",
    "        # return(len(s))\r\n",
    "\r\n",
    "        n = len(apples)\r\n",
    "        ans = 0\r\n",
    "        i = 0\r\n",
    "        heap = []\r\n",
    "        while(i < n or heap):\r\n",
    "            if i < n and apples[i]:\r\n",
    "                heapq.heappush(heap, [i + days[i], apples[i]])\r\n",
    "            \r\n",
    "            while heap and (heap[0][0] <= i or heap[0][1] == 0):\r\n",
    "                heapq.heappop(heap)\r\n",
    "            \r\n",
    "            if heap:\r\n",
    "                heap[0] = [heap[0][0], heap[0][1] - 1]\r\n",
    "                ans += 1\r\n",
    "            \r\n",
    "            i += 1\r\n",
    "\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        n = len(apples)\n",
    "        heap = []\n",
    "        result = 0\n",
    "        i = 0\n",
    "        while(i < n or heap):\n",
    "            if(i < n and apples[i] > 0):\n",
    "                heapq.heappush(heap, [i+days[i], apples[i]])\n",
    "            if(heap):\n",
    "                d, cnt = heapq.heappop(heap)\n",
    "                while(heap and d <= i):\n",
    "                    d, cnt = heapq.heappop(heap)\n",
    "                if(i < d):\n",
    "                    result += 1\n",
    "                    cnt -= 1\n",
    "                    if(cnt > 0):\n",
    "                        heapq.heappush(heap, [d,cnt])\n",
    "            i += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        tmp = []     \n",
    "        n = len(apples)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            heapq.heappush(tmp, [i+days[i], apples[i]])\n",
    "            while tmp:\n",
    "                if i < tmp[0][0] and tmp[0][1]:\n",
    "                    res += 1\n",
    "                    tmp[0][1] -= 1\n",
    "                    break\n",
    "                else:\n",
    "                    heapq.heappop(tmp)\n",
    "\n",
    "        while tmp:\n",
    "            if n < tmp[0][0] and tmp[0][1]:\n",
    "                res += 1\n",
    "                tmp[0][1] -= 1\n",
    "                n += 1\n",
    "            else:\n",
    "                heapq.heappop(tmp)  \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pq = []  #存【第i天，过期的苹果数量】\n",
    "        i = 0\n",
    "        while i < len(apples):\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heapq.heappop(pq)\n",
    "            if apples[i]:\n",
    "                heapq.heappush(pq, [i+days[i], apples[i]])\n",
    "            if pq:\n",
    "                pq[0][1] -= 1\n",
    "                if pq[0][1] == 0:\n",
    "                    heapq.heappop(pq)\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        while pq:\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heapq.heappop(pq)\n",
    "            if len(pq) == 0:\n",
    "                break\n",
    "            p = heapq.heappop(pq)\n",
    "            num = min(p[0]-i,p[1])\n",
    "            ans += num\n",
    "            i+=num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\r\n",
    "        # # 超时\r\n",
    "        # lis = [[i, -1] for i in range(len(days))]\r\n",
    "        # for i in range(len(days)):\r\n",
    "        #     if days[i] != 0:\r\n",
    "        #         lis[i][1] = i + days[i] - 1\r\n",
    "        # arr = sorted(lis, key=lambda x:(x[1], x[0]))\r\n",
    "        # print(arr)\r\n",
    "\r\n",
    "        # s = set()\r\n",
    "        # for i in range(len(arr)):\r\n",
    "        #     cnt = 0\r\n",
    "        #     if arr[i][1] != -1:\r\n",
    "        #         for k in range(arr[i][0], arr[i][1] + 1):\r\n",
    "        #             if cnt < apples[arr[i][0]]:\r\n",
    "        #                 if k not in s:\r\n",
    "        #                     s.add(k)\r\n",
    "        #                     cnt += 1\r\n",
    "        #             else:\r\n",
    "        #                 break\r\n",
    "\r\n",
    "        # return(len(s))\r\n",
    "\r\n",
    "        n = len(apples)\r\n",
    "        ans = 0\r\n",
    "        i = 0\r\n",
    "        heap = []\r\n",
    "        while(i < n or heap):\r\n",
    "            if i < n and apples[i]:\r\n",
    "                heapq.heappush(heap, [i + days[i], apples[i]])\r\n",
    "            \r\n",
    "            while heap and (heap[0][0] <= i or heap[0][1] == 0):\r\n",
    "                heapq.heappop(heap)\r\n",
    "            \r\n",
    "            if heap:\r\n",
    "                heap[0] = [heap[0][0], heap[0][1] - 1]\r\n",
    "                ans += 1\r\n",
    "            \r\n",
    "            i += 1\r\n",
    "\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "\n",
    "        p = []\n",
    "        i = 0\n",
    "        ans = 0\n",
    "\n",
    "        while i < len(apples):\n",
    "\n",
    "            while p and p[0][0] <= i:\n",
    "                heapq.heappop(p)\n",
    "\n",
    "            if apples[i]:\n",
    "                tmp = [days[i] + i, apples[i]]\n",
    "                heapq.heappush(p, tmp)\n",
    "\n",
    "            if p and p[0][1]:\n",
    "                p[0][1] -= 1\n",
    "                ans += 1\n",
    "                if not p[0][1]:\n",
    "                    heapq.heappop(p)\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        while p:\n",
    "            while p and p[0][0] < i:\n",
    "                heapq.heappop(p)\n",
    "\n",
    "            if len(p) == 0:\n",
    "                break\n",
    "\n",
    "            ans += min(p[0][1], p[0][0] - i)\n",
    "            i += min(p[0][1], p[0][0] - i)\n",
    "            heapq.heappop(p)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        apple_list = []\n",
    "        num = 0\n",
    "        for i in range(len(apples)):\n",
    "            heapq.heappush(apple_list, [i + days[i], apples[i]])\n",
    "            \n",
    "            while len(apple_list) and apple_list[0][0] <= i:\n",
    "                heapq.heappop(apple_list)\n",
    "\n",
    "            if len(apple_list):\n",
    "                apple_list[0][1] -= 1\n",
    "                num += 1\n",
    "                if apple_list[0][1] == 0:\n",
    "                    heapq.heappop(apple_list)\n",
    "        \n",
    "        i = len(apples)\n",
    "        while len(apple_list):\n",
    "            while len(apple_list) and apple_list[0][0] <= i:\n",
    "                heapq.heappop(apple_list)\n",
    "            if len(apple_list):\n",
    "                i += min(apple_list[0][0]-i, apple_list[0][1])\n",
    "                heapq.heappop(apple_list)\n",
    "\n",
    "        num += i-len(apples)\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        pq = []\n",
    "        heapify(pq)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        while i < len(apples) or pq:\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heappop(pq)\n",
    "            if i < len(apples) and apples[i] != 0:\n",
    "                heappush(pq,[days[i]+i,apples[i]])\n",
    "            if pq:\n",
    "                pq[0][1] -= 1\n",
    "                res += 1\n",
    "                if not pq[0][1]:\n",
    "                    heappop(pq)\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        pq = []\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < len(apples):\n",
    "            # verify on the date \n",
    "            while pq and pq[0][0] <= i:\n",
    "                heappop(pq)\n",
    "            if apples[i] > 0:\n",
    "                heappush(pq, [i + days[i], apples[i]])\n",
    "            if pq:\n",
    "                pq[0][1] -= 1\n",
    "                if pq[0][1] == 0:\n",
    "                    heappop(pq)\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        while pq:\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heappop(pq)\n",
    "            if len(pq) == 0:\n",
    "                break\n",
    "            p = heappop(pq)\n",
    "            num = min(p[0] - i, p[1])\n",
    "            ans += num\n",
    "            i += num\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        n = len(apples)\n",
    "        ans = 0\n",
    "        day = 0\n",
    "        t = []\n",
    "        while day < n:\n",
    "            if day<n:\n",
    "                heappush(t,[day+days[day],apples[day]]) # add new expire day\n",
    "            while t and (t[0][0] <= day or t[0][1] == 0): # remove expire day\n",
    "                heappop(t)\n",
    "            if t:\n",
    "                t[0][1]-=1\n",
    "                ans += 1\n",
    "            day += 1\n",
    "        while t:\n",
    "            while t and (t[0][0] <= day or t[0][1] == 0):\n",
    "                heappop(t)\n",
    "            if not t:break\n",
    "            now = heappop(t)\n",
    "            temp = min(now[1],now[0]-day)\n",
    "            ans += temp\n",
    "            day += temp\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        #堆+贪心 优先队列\n",
    "        pq = [] #最小堆，队首是最小的 [i+days[i], apples[i]]\n",
    "        i = 0 #天数\n",
    "        ans = 0 #可以吃到的苹果数\n",
    "\n",
    "        #第一阶段 i <= n\n",
    "        while i < len(apples):\n",
    "            while pq and pq[0][0] <= i: #腐烂日期小于当前日期（=是因为i从0开始）\n",
    "                heappop(pq) #出队列，没用了\n",
    "            if apples[i] > 0: #当天生产苹果，入队列\n",
    "                heappush(pq, [i + days[i], apples[i]])\n",
    "            if pq: #还有苹果可吃\n",
    "                pq[0][1] -= 1\n",
    "                ans += 1 #吃苹果\n",
    "                if pq[0][1] == 0:\n",
    "                    heappop(pq)\n",
    "            i += 1\n",
    "        \n",
    "        #第二阶段 i > n时，不产苹果只消耗\n",
    "        while pq:\n",
    "            cur = heappop(pq)\n",
    "            res = min(cur[0]-i, cur[1])\n",
    "            i += res #当前天数加上去\n",
    "            ans += res #吃的苹果数直接加上去\n",
    "            while pq and pq[0][0] <= i: #再判断是否腐烂\n",
    "                heappop(pq)\n",
    "        # print(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        n = len(apples)\n",
    "        apple_list = []\n",
    "        num = 0\n",
    "        for i in range(n):\n",
    "            if apples[i] > 0:\n",
    "                heapq.heappush(apple_list, [i + days[i], apples[i]])\n",
    "            \n",
    "            while apple_list and apple_list[0][0] <= i:\n",
    "                heapq.heappop(apple_list)\n",
    "\n",
    "            if apple_list:\n",
    "                apple_list[0][1] -= 1\n",
    "                num += 1\n",
    "                if apple_list[0][1] == 0:\n",
    "                    heapq.heappop(apple_list)\n",
    "        \n",
    "        i = n\n",
    "        while apple_list:\n",
    "            while apple_list and apple_list[0][0] <= i:\n",
    "                heapq.heappop(apple_list)\n",
    "            if apple_list:\n",
    "                i += min(apple_list[0][0]-i, apple_list[0][1])\n",
    "                heapq.heappop(apple_list)\n",
    "\n",
    "        num += i-n\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 0元素不需要进队列，而且0元素可能出现在第一个\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        import heapq\n",
    "        l = len(apples)\n",
    "        p = []\n",
    "        cnt = 0\n",
    "        w = 0 \n",
    "        while p or cnt < l:\n",
    "            #for i in range(len(p)):#将这个去掉，通过保存的days[i]元素直接进行判断\n",
    "            #    p[i][0] -= 1\n",
    "            while p:\n",
    "                if p[0][0] <= cnt or p[0][1] <=0:\n",
    "                    heapq.heappop(p)\n",
    "                else:\n",
    "                    break\n",
    "            if cnt < l and apples[cnt]:\n",
    "                heapq.heappush(p, [days[cnt]+cnt, apples[cnt]])\n",
    "            #print(p)\n",
    "            while p:#确认消费后是否存在已经消费完的节点，移除队列\n",
    "                if p[0][1] <=0:\n",
    "                    heapq.heappop(p)\n",
    "                else:\n",
    "                    w+=1#新一轮消费1个苹果\n",
    "                    p[0][1] -=1\n",
    "                    if p[0][1] == 0:\n",
    "                        heapq.heappop(p)\n",
    "                    break\n",
    "            cnt +=1\n",
    "        #print(p,w)\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        dp = []\n",
    "        n = len(apples)\n",
    "        i,res = 0,0\n",
    "        while dp or i<n:\n",
    "            if i<n:\n",
    "                heapq.heappush(dp,[days[i]+i,apples[i]])\n",
    "            while dp and (dp[0][1]<=0 or dp[0][0]<=i):\n",
    "                heapq.heappop(dp)\n",
    "            if dp:\n",
    "                res+=1\n",
    "                dp[0][1]-=1\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        n = len(apples)\n",
    "        eaten = 0\n",
    "        i = 0\n",
    "        heap = []\n",
    "        while i < n or heap:\n",
    "            if i < n and apples[i] > 0:\n",
    "                heapq.heappush(heap, [i + days[i] - 1, apples[i]])\n",
    "\n",
    "            while heap and heap[0][0] < i:\n",
    "                heapq.heappop(heap)\n",
    "\n",
    "            if heap:\n",
    "                day, apple = heapq.heappop(heap)\n",
    "                if apple - 1 > 0 and day > i:\n",
    "                    heapq.heappush(heap, [day, apple - 1])\n",
    "                eaten += 1\n",
    "            i += 1\n",
    "        return eaten\n",
    "\n",
    "\n",
    "# 首先，如果「time<n」或者「堆不为空」，说明「还有苹果未被生成」或者「未必吃掉」，继续模拟；\n",
    "# 在当日模拟中，如果「time<n」，说明当天有苹果生成，先将苹果 以二元组 (time+days[time]−1,apples[time]) 形式加入小根堆中；\n",
    "# 其中二元组表示 (最后食用日期,当日产生苹果数量)(最后食用日期, 当日产生苹果数量)(最后食用日期,当日产生苹果数量)，同时需要过滤 apples[time]=0 的情况。\n",
    "# 然后尝试从堆中取出「最后食用日期」最早「可食用」的苹果 cur，如果堆顶元素已过期，则抛弃；\n",
    "# 如果吃掉 cur 一个苹果后，仍有剩余，并且最后时间大于当前时间（尚未过期），将 cur 重新入堆；\n",
    "# 循环上述逻辑，直到所有苹果出堆。\n",
    "\n",
    "# class Solution:\n",
    "#     def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "#         i = 0\n",
    "#         heap = []\n",
    "#         eaten = 0\n",
    "#         n = len(apples)\n",
    "#         while i < n or heap:\n",
    "#             if i < n and apples[i] > 0:\n",
    "#                 # 为什么要减1\n",
    "#                 # 这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂\n",
    "#                 # i + days[i] 就过期了 所以要减1\n",
    "#                 # heapq.heappush(heap, [i + days[i] , apples[i]])\n",
    "#                 heapq.heappush(heap, [i + days[i] - 1, apples[i]])\n",
    "#             while heap and heap[0][0] < i:\n",
    "#                 heapq.heappop(heap)\n",
    "#             if heap:\n",
    "#                 day, apple = heapq.heappop(heap)\n",
    "#                 if day > i and apple - 1 > 0:\n",
    "#                     heapq.heappush(heap, [day, apple - 1])\n",
    "#                 eaten += 1\n",
    "#             i += 1\n",
    "#         return eaten\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pq = [] # 优先队列 二元组（time, cnt） 腐烂日期，腐烂苹果总量 \n",
    "        i = 0\n",
    "        while i < len(apples):\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heappop(pq)\n",
    "            \n",
    "            if apples[i]:\n",
    "                heappush(pq, [i + days[i], apples[i]])\n",
    "            \n",
    "            if pq:\n",
    "                pq[0][1] -= 1\n",
    "                if pq[0][1] == 0:\n",
    "                    heappop(pq)\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        \n",
    "        while pq:\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heappop(pq)\n",
    "            if len(pq) == 0:\n",
    "                return ans\n",
    "            p = heappop(pq)\n",
    "            num = min(p[0] - i, p[1])\n",
    "            ans += num\n",
    "            i += num\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 0元素不需要进队列，而且0元素可能出现在第一个\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        import heapq\n",
    "        l = len(apples)\n",
    "        p = []\n",
    "        cnt = 0\n",
    "        w = 0 \n",
    "        while p or cnt < l:\n",
    "            #for i in range(len(p)):#将这个去掉，通过保存的days[i]元素直接进行判断,否则会超时\n",
    "            #    p[i][0] -= 1\n",
    "            while p:\n",
    "                if p[0][0] <= cnt or p[0][1] <=0:\n",
    "                    heapq.heappop(p)\n",
    "                else:\n",
    "                    break\n",
    "            if cnt < l and apples[cnt]:\n",
    "                heapq.heappush(p, [days[cnt]+cnt, apples[cnt]])\n",
    "            #print(p)\n",
    "            while p:#确认消费后是否存在已经消费完的节点，移除队列\n",
    "                if p[0][1] <=0:\n",
    "                    heapq.heappop(p)\n",
    "                else:\n",
    "                    w+=1#新一轮消费1个苹果\n",
    "                    p[0][1] -=1\n",
    "                    if p[0][1] == 0:\n",
    "                        heapq.heappop(p)\n",
    "                    break\n",
    "            cnt +=1\n",
    "        #print(p,w)\n",
    "        return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        appleBasket = []\n",
    "        ans = 0\n",
    "        for i, (n, day) in enumerate(zip(apples, days)):    \n",
    "            heapq.heappush(appleBasket, [i + day, n])\n",
    "            while appleBasket:\n",
    "                ddl, k = heapq.heappop(appleBasket)\n",
    "                if ddl > i:\n",
    "                    ans += 1\n",
    "                    k -= 1\n",
    "                    if k > 0:\n",
    "                        heapq.heappush(appleBasket, [ddl, k])\n",
    "                    break\n",
    "\n",
    "        endDay = len(days)\n",
    "        while appleBasket:\n",
    "            ddl, k = heapq.heappop(appleBasket)\n",
    "            if ddl > endDay:\n",
    "                endDay_ = min(ddl, endDay + k)\n",
    "                inc = endDay_ - endDay\n",
    "                endDay = endDay_\n",
    "                ans += inc\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        pq, i, ans = [], 0, 0\n",
    "        while i < len(apples) or pq:\n",
    "            while pq and pq[0][0] <= i:\n",
    "                heapq.heappop(pq)\n",
    "            if i < len(apples) and apples[i]:\n",
    "                heapq.heappush(pq, [i + days[i], apples[i]])\n",
    "            if pq:\n",
    "                pq[0][1]-=1\n",
    "                ans += 1\n",
    "                if not pq[0][1]:\n",
    "                    heapq.heappop(pq)\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        result = 0\n",
    "        import heapq\n",
    "\n",
    "        nums = []\n",
    "        day = 0\n",
    "        while len(nums) or day < len(days):\n",
    "            if len(nums) == 0 and apples[day] == 0:\n",
    "                day += 1\n",
    "                continue\n",
    "            if day < len(days) and apples[day] != 0:\n",
    "                heappush(nums, [day + days[day], apples[day]])\n",
    "\n",
    "            top = nums[0]\n",
    "            result += 1\n",
    "            day += 1\n",
    "            nums[0][1] -= 1\n",
    "\n",
    "            while len(nums) and nums[0][1] == 0:\n",
    "                heapq.heappop(nums)\n",
    "            while len(nums) and nums[0][0] <= day:\n",
    "                heapq.heappop(nums)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        #维护小根堆+贪心(优先吃最先过期的)\n",
    "        h,ans=[],0\n",
    "        for i,x in enumerate(apples):\n",
    "            heapq.heappush(h,[i+days[i],x])\n",
    "            while h and (h[0][0]<=i or h[0][1]==0):\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                ans+=1\n",
    "                h[0][1]-=1\n",
    "        i=len(apples)\n",
    "        while h:\n",
    "            while h and (h[0][0]<=i or h[0][1]==0):\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                ans+=1\n",
    "                h[0][1]-=1\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        n = len(apples)\n",
    "        ans = 0\n",
    "        day = 0\n",
    "        t = []\n",
    "        cur = defaultdict(int)\n",
    "        while day < n or t:\n",
    "            if day<n:\n",
    "                cur[day+days[day]] += apples[day] # add new apples\n",
    "                heappush(t,day+days[day]) # add new expire day\n",
    "            while len(t)>0 and (t[0] <= day or cur[t[0]] == 0): # remove expire day\n",
    "                if t[0] in cur:\n",
    "                    del cur[t[0]]\n",
    "                heappop(t)\n",
    "            if t:\n",
    "                cur[t[0]] -= 1\n",
    "                ans += 1\n",
    "            day += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        #维护小根堆\n",
    "        h,ans=[],0\n",
    "        for i,x in enumerate(apples):\n",
    "            heapq.heappush(h,[i+days[i],x])\n",
    "            while h and (h[0][0]<=i or h[0][1]==0):\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                ans+=1\n",
    "                h[0][1]-=1\n",
    "        i=len(apples)\n",
    "        while h:\n",
    "            while h and (h[0][0]<=i or h[0][1]==0):\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                ans+=1\n",
    "                h[0][1]-=1\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        #维护小根堆\n",
    "        h,ans=[],0\n",
    "        for i,x in enumerate(apples):\n",
    "            heapq.heappush(h,[i+days[i],x])\n",
    "            while h and (h[0][0]<=i or h[0][1]==0):\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                ans+=1\n",
    "                h[0][1]-=1\n",
    "        i=len(apples)\n",
    "        while h:\n",
    "            while h and (h[0][0]<=i or h[0][1]==0):\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                ans+=1\n",
    "                h[0][1]-=1\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush,heappop\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: list[int], days: list[int]) -> int:\n",
    "        '''\n",
    "        基本思想就是 将时间分割成两部分\n",
    "        取苹果+吃苹果:\n",
    "               取苹果-放入框里面-并记录当前日期与过期日期-将框放入堆中\n",
    "               将已经过期的框直接取出放弃\n",
    "               吃苹果-从堆中取出最快过期的框-并吃掉一个-检查框里面还有没有苹果-如果还有就放回堆中\n",
    "        吃苹果:\n",
    "               吃苹果-从堆中取出最快过期的框-并吃掉一个-检查框里面还有没有苹果-如果还有就放回堆中\n",
    "        :param apples:\n",
    "        :param days:\n",
    "        :return:\n",
    "        '''\n",
    "        now = 1\n",
    "        heapList = []\n",
    "        count = 0\n",
    "        for iterNum in range(len(apples)):\n",
    "            tmp = [days[iterNum]+now,apples[iterNum]]\n",
    "            heappush(heapList,tmp)\n",
    "            while True:\n",
    "                if len(heapList)==0:\n",
    "                    break\n",
    "                single = heappop(heapList)\n",
    "                if single[0]<=now:\n",
    "                    continue\n",
    "                else:\n",
    "                    single[1] = single[1]-1\n",
    "                    count+=1\n",
    "                    if single[1]>0:\n",
    "                        heappush(heapList,single)\n",
    "                    break\n",
    "                pass\n",
    "            now+=1\n",
    "            pass\n",
    "        while True:\n",
    "            if len(heapList) == 0:\n",
    "                break\n",
    "            single = heappop(heapList)\n",
    "            if single[0] <= now:\n",
    "                continue\n",
    "            else:\n",
    "                single[1] = single[1] - 1\n",
    "                count += 1\n",
    "                if single[1] > 0:\n",
    "                    heappush( heapList,single)\n",
    "            now+=1\n",
    "            pass\n",
    "        return count\n",
    "    pass\n",
    "\n",
    "Solution().eatenApples([3,0,0,0,0,2],[3,0,0,0,0,2])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        n = len(apples)\n",
    "        ans = 0\n",
    "        day = 0\n",
    "        t = []\n",
    "        cur = defaultdict(int)\n",
    "        while day < n or t:\n",
    "            if day<n:\n",
    "                cur[day+days[day]] += apples[day] # add new apples\n",
    "                heappush(t,day+days[day]) # add new expire day\n",
    "            while t and (t[0] <= day or cur[t[0]] == 0): # remove expire day\n",
    "                heappop(t)\n",
    "            if t:\n",
    "                cur[t[0]] -= 1\n",
    "                ans += 1\n",
    "            day += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "        cnt = SortedList(key=lambda x: x[0] + x[1])\n",
    "        day, ans = 0, 0\n",
    "        n = len(apples)\n",
    "        while day < n or len(cnt):\n",
    "            # print(cnt)\n",
    "            while len(cnt) and (cnt[0][0] + cnt[0][1] <= day or apples[cnt[0][0]] == 0): cnt.pop(0)\n",
    "            if day < n and apples[day]: cnt.add((day, days[day]))\n",
    "            if len(cnt): \n",
    "                ans += 1\n",
    "                apples[cnt[0][0]] -= 1\n",
    "            day += 1\n",
    "            # print(day)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "import sys \n",
    "# 小顶堆优先队列\n",
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.queue = []\n",
    " \n",
    "    # 获取优先队列中元素个数\n",
    "    def qsize(self):\n",
    "        return len(self.queue)\n",
    " \n",
    "    # 入队\n",
    "    def put(self, ele):\n",
    "        heapq.heappush(self.queue, ele)\n",
    " \n",
    "    # 出队\n",
    "    def get(self):\n",
    "        return heapq.heappop(self.queue)\n",
    "\n",
    "class Apple:\n",
    "    def __init__(self, apple, day):\n",
    "        self.apple = apple\n",
    "        self.day = day\n",
    " \n",
    "    def __lt__(self, other):\n",
    "        return self.day < other.day\n",
    " \n",
    " \n",
    "class Solution(object):\n",
    "    def eatenApples(self, apples, days):\n",
    "        \"\"\"\n",
    "        :type apples: List[int]\n",
    "        :type days: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        pq = PriorityQueue()\n",
    "        count = 0\n",
    " \n",
    "        i = 0\n",
    "        while i < len(apples) or len(pq.queue) > 0:\n",
    "            if i < len(apples) and apples[i] > 0:\n",
    "                pq.put(Apple(apples[i], i + days[i]))\n",
    " \n",
    "            while True:\n",
    "                if len(pq.queue) == 0:\n",
    "                    break\n",
    " \n",
    "                head = pq.queue[0]\n",
    "                if head.day <= i or head.apple == 0:\n",
    "                    pq.get()\n",
    "                    continue\n",
    "                else:\n",
    "                    head.apple -= 1\n",
    "                    count += 1\n",
    "                    break\n",
    " \n",
    "            i += 1\n",
    " \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "import sys \n",
    "# 小顶堆优先队列\n",
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.queue = []\n",
    " \n",
    "    # 获取优先队列中元素个数\n",
    "    def qsize(self):\n",
    "        return len(self.queue)\n",
    " \n",
    "    # 入队\n",
    "    def put(self, ele):\n",
    "        heapq.heappush(self.queue, ele)\n",
    " \n",
    "    # 出队\n",
    "    def get(self):\n",
    "        return heapq.heappop(self.queue)\n",
    "\n",
    "class Apple:\n",
    "    def __init__(self, apple, day):\n",
    "        self.apple = apple\n",
    "        self.day = day\n",
    " \n",
    "    def __lt__(self, other):\n",
    "        return self.day < other.day\n",
    " \n",
    " \n",
    "class Solution(object):\n",
    "    def eatenApples(self, apples, days):\n",
    "        \"\"\"\n",
    "        :type apples: List[int]\n",
    "        :type days: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        pq = PriorityQueue()\n",
    "        count = 0\n",
    " \n",
    "        i = 0\n",
    "        while i < len(apples) or len(pq.queue) > 0:\n",
    "            if i < len(apples) and apples[i] > 0:\n",
    "                pq.put(Apple(apples[i], i + days[i]))\n",
    " \n",
    "            while True:\n",
    "                if len(pq.queue) == 0:\n",
    "                    break\n",
    " \n",
    "                head = pq.queue[0]\n",
    "                if head.day <= i or head.apple == 0:\n",
    "                    pq.get()\n",
    "                    continue\n",
    "                else:\n",
    "                    head.apple -= 1\n",
    "                    count += 1\n",
    "                    break\n",
    " \n",
    "            i += 1\n",
    " \n",
    "        return count\n",
    "#apples=''\n",
    "#days=''\n",
    "#apples=sys.stdin.readline().strip()\n",
    "#apples=apples.lstrip('[')\n",
    "#apples=apples.rstrip(']')\n",
    "#apples=apples.split(',')\n",
    "#apples=[int(x) for x in apples]\n",
    "#print(apples)\n",
    "\n",
    "#days=sys.stdin.readline().strip()\n",
    "#days=days.lstrip('[')\n",
    "#days=days.rstrip(']')\n",
    "#days=days.split(',')\n",
    "#days=[int(x) for x in days]\n",
    "#print(days)\n",
    "\n",
    "#S=Solution()\n",
    "#result = S.eatenApples(apples,days)\n",
    "#print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eatenApples(self, apples: List[int], days: List[int]) -> int:\n",
    "\n",
    "        cnt = defaultdict(int)\n",
    "        minexp = inf\n",
    "        ans = 0\n",
    "        total = 0\n",
    "        for i, (a, d) in enumerate(zip(apples, days)):\n",
    "            total -= cnt[i]\n",
    "            cnt[i] = 0\n",
    "            cnt[i+d] += a\n",
    "            total += a\n",
    "            if a > 0: minexp = min(minexp, i+d)\n",
    "            if total > 0:\n",
    "                ans += 1\n",
    "                while cnt[minexp] == 0:\n",
    "                    minexp += 1\n",
    "                cnt[minexp] -= 1\n",
    "                total -= 1\n",
    "        for i in range(len(apples), 40100):\n",
    "            total -= cnt[i]\n",
    "            cnt[i] = 0\n",
    "            if total > 0:\n",
    "                ans += 1\n",
    "                while cnt[minexp] == 0:\n",
    "                    minexp += 1\n",
    "                cnt[minexp] -= 1\n",
    "                total -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "import sys \n",
    "# 小顶堆优先队列\n",
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.queue = []\n",
    " \n",
    "    # 获取优先队列中元素个数\n",
    "    def qsize(self):\n",
    "        return len(self.queue)\n",
    " \n",
    "    # 入队\n",
    "    def put(self, ele):\n",
    "        heapq.heappush(self.queue, ele)\n",
    " \n",
    "    # 出队\n",
    "    def get(self):\n",
    "        return heapq.heappop(self.queue)\n",
    "\n",
    "class Apple:\n",
    "    def __init__(self, apple, day):\n",
    "        self.apple = apple\n",
    "        self.day = day\n",
    " \n",
    "    def __lt__(self, other):\n",
    "        return self.day < other.day\n",
    " \n",
    " \n",
    "class Solution(object):\n",
    "    def eatenApples(self, apples, days):\n",
    "        \"\"\"\n",
    "        :type apples: List[int]\n",
    "        :type days: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        pq = PriorityQueue()\n",
    "        count = 0\n",
    " \n",
    "        i = 0\n",
    "        while i < len(apples) or len(pq.queue) > 0:\n",
    "            if i < len(apples) and apples[i] > 0:\n",
    "                pq.put(Apple(apples[i], i + days[i]))\n",
    " \n",
    "            while True:\n",
    "                if len(pq.queue) == 0:\n",
    "                    break\n",
    " \n",
    "                head = pq.queue[0]\n",
    "                if head.day <= i or head.apple == 0:\n",
    "                    pq.get()\n",
    "                    continue\n",
    "                else:\n",
    "                    head.apple -= 1\n",
    "                    count += 1\n",
    "                    break\n",
    " \n",
    "            i += 1\n",
    " \n",
    "        return count\n",
    "#apples=''\n",
    "#days=''\n",
    "#apples=sys.stdin.readline().strip()\n",
    "#apples=apples.lstrip('[')\n",
    "#apples=apples.rstrip(']')\n",
    "#apples=apples.split(',')\n",
    "#apples=[int(x) for x in apples]\n",
    "#print(apples)\n",
    "\n",
    "#days=sys.stdin.readline().strip()\n",
    "#days=days.lstrip('[')\n",
    "#days=days.rstrip(']')\n",
    "#days=days.split(',')\n",
    "#days=[int(x) for x in days]\n",
    "#print(days)\n",
    "\n",
    "#S=Solution()\n",
    "#result = S.eatenApples(apples,days)\n",
    "#print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "#import sys \n",
    "# 小顶堆优先队列\n",
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.queue = []\n",
    " \n",
    "    # 获取优先队列中元素个数\n",
    "    def qsize(self):\n",
    "        return len(self.queue)\n",
    " \n",
    "    # 入队\n",
    "    def put(self, ele):\n",
    "        heapq.heappush(self.queue, ele)\n",
    " \n",
    "    # 出队\n",
    "    def get(self):\n",
    "        return heapq.heappop(self.queue)\n",
    "\n",
    "class Apple:\n",
    "    def __init__(self, apple, day):\n",
    "        self.apple = apple\n",
    "        self.day = day\n",
    " \n",
    "    def __lt__(self, other):\n",
    "        return self.day < other.day\n",
    " \n",
    " \n",
    "class Solution(object):\n",
    "    def eatenApples(self, apples, days):\n",
    "        \"\"\"\n",
    "        :type apples: List[int]\n",
    "        :type days: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        pq = PriorityQueue()\n",
    "        count = 0\n",
    " \n",
    "        i = 0\n",
    "        while i < len(apples) or len(pq.queue) > 0:\n",
    "            if i < len(apples) and apples[i] > 0:\n",
    "                pq.put(Apple(apples[i], i + days[i]))\n",
    " \n",
    "            while True:\n",
    "                if len(pq.queue) == 0:\n",
    "                    break\n",
    " \n",
    "                head = pq.queue[0]\n",
    "                if head.day <= i or head.apple == 0:\n",
    "                    pq.get()\n",
    "                    continue\n",
    "                else:\n",
    "                    head.apple -= 1\n",
    "                    count += 1\n",
    "                    break\n",
    " \n",
    "            i += 1\n",
    " \n",
    "        return count\n",
    "#apples=''\n",
    "#days=''\n",
    "#apples=sys.stdin.readline().strip()\n",
    "#apples=apples.lstrip('[')\n",
    "#apples=apples.rstrip(']')\n",
    "#apples=apples.split(',')\n",
    "#apples=[int(x) for x in apples]\n",
    "#print(apples)\n",
    "\n",
    "#days=sys.stdin.readline().strip()\n",
    "#days=days.lstrip('[')\n",
    "#days=days.rstrip(']')\n",
    "#days=days.split(',')\n",
    "#days=[int(x) for x in days]\n",
    "#print(days)\n",
    "\n",
    "#S=Solution()\n",
    "#result = S.eatenApples(apples,days)\n",
    "#print(result)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
